package com.xsq.worker101.study;

/**
 * @ClassName Work
 * @Description TODO
 * @Author xsq
 * @Date 2021/2/4 14:20
 **/
public class Work {
    /**
     * 判断数组中所有的数字是否只出现一次。给定一个数组array，
     * 判断数组 array 中是否所有的数字都只 出现过一次。例如，arr = {1, 2, 3}，
     * 输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。
     * 这里测试的是没有偏移量的,如果不连续和取值范围过大会造成数组过大就需要偏移量
     */
    public static  void test1(){
        int[] arr1  = {1,2,3};
        System.out.println(worker1(arr1));
        int[] arr2  = {1,2,1};
        System.out.println(worker1(arr2));
    }

    /**
     * // 计数法思路，使用boolean 数组存储值，循环遍历依次放入数组，判断如存在则说明重复
     * @param arr
     * @return
     */
    public static boolean worker1(int[] arr){
        boolean[] bo  = new boolean[arr.length+1];
        for (int i = 0; i <arr.length ; i++) {
            if(bo[arr[i]]){
                return false;
            }else{
                bo[arr[i]] =true;
            }
        }
        return true;
    }

    public static  void test2(){
        // TODO Auto-generated method stub
        int w = 10;
        int[] p = {5, 5, 3, 4 ,3};
        int[] g = {400, 500, 200, 300 ,350};
        System.out.println(" 最优收益：" + getBestGoldMining(w, p, g));
    }

    /**
     * 很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不 同。
     * 例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，
     * 需要3个工人 来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，
     * 要么不挖，不能派出一半人挖取一半的金矿。要 求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
     * @param w
     * @param p
     * @param g
     * @return
     */
    public static int getBestGoldMining(int w, int[] p, int[] g) {
        int[][] result=new int[g.length+1][w+1];

        for(int i=1; i<=g.length; i++) {
            for(int j=1; j<=w; j++) {
                if(j<p[i-1]) {
                    result[i][j]=result[i-1][j];
                }
                else
                {
                    result[i][j]=Math.max(result[i-1][j], result[i-1][j-p[i-1]]+g[i-1]);
                }
            }
        }
        return result[g.length][w];
    }


    public static void main(String[] args) {
        test1();
        test2();
    }
}
